Transactions on Combinatorics
Volume:13 Issue: 3, Sep 2024

Trees are acyclic connected graphs. Plane trees, $d$-ary trees, binary trees, noncrossing trees and their generalizations, which are families of trees, have been enumerated by many authors using various statistics. These trees are known to be enumerated by Catalan or Catalan-like formulas (Fuss-Catalan numbers). One of the most common approaches to the enumeration of these trees is by means of generating functions. Another method that can be used to enumerate them is by constructing bijections between sets of the same cardinality. The bijective method is preferred to other methods by many combinatorialists. So, in this paper, we construct bijections relating $k$-plane trees, $k$-noncrossing increasing trees, $k$-noncrossing trees, $k$-binary trees and weakly labelled $k$-trees.

Let $G=(V, E)$ be a simple graph with vertex set $V$ and edge set $E$. A {\em total Roman dominating function} on a graph $G$ is a function $f:V\rightarrow \{0,1,2\}$ satisfying the following conditions: (i) every vertex $u$ {\color{blue}such that} $f(u)=0$ is adjacent to at least one vertex $v$ {\color{blue}such that} $f(v)=2$ and (ii) the subgraph of $G$ induced by the set of all vertices of positive weight has no isolated vertex. The weight of a total Roman dominating function $f$ is the value, $f(V)=\Sigma_{u\in V(G)}f(u)$. The {\em total Roman domination number} $\gamma_{tR}(G)$ of $G$ is the minimum weight of a total Roman dominating function of $G$. A subset $S$ of $V$ is a $2$-independent set of $G$ if every vertex of $S$ has at most one neighbor in $S$. The maximum cardinality of a $2$-independent set of $G$ is the $2$-independence number $\beta_2(G)$. These two parameters are incomparable in general, however, we show that if $T$ is a tree, then $\gamma_{tR}(T)\le \frac{3}{2}\beta_2(T)$ and we characterize all trees attaining the equality.

Let $G^\sigma$ be an oriented graph with underlying simple graph $G$. The skew-adjacency matrix of $G^\sigma$ is the $\{0, 1, -1\}$-matrix $S=S(G^\sigma)=[s_{ij}]$, such that $s_{ij}=1$ if $(v_i, v_j)$ is an arc in $G^\sigma$, $s_{ij}=-1$ if $(v_j, v_i)$ is an arc in $G^\sigma$ and $s_{ij}=0$, otherwise. In this paper, all connected oriented graphs with three distinct skew-eigenvalues $0$ and $\pm 2 \mathbf{i}$ are characterized.

The eccentricity matrix $\varepsilon(G)$ of a graph $G$ is defined as \begin{equation}\varepsilon(G)_{uv}= \begin{cases}d_{uv} & d_{uv}=min\{e(u),e(v)\},\\0 & d_{uv} < min\{e(u),e(v)\}. \notag\end{cases}\end{equation} Let $T_t$ be a $t$-clique tree corresponding to the tree $T($underlying graph of $T_t)$ with order $n'=(n-1)t+1$ and diameter $d$. In this paper, we identify the extremal $t$-clique trees with given diameter having the minimum $\varepsilon$-spectral radius. Simultaneously, we calculate the lower bound of $\varepsilon$-spectral radius of $t$-clique trees when $n-d$ is odd.

In $2011$, Beeler and Hoilman generalized the game of peg solitaire to arbitrary connected graphs. Since then peg solitaire and related games have been considered on many graph classes. One of the main goals is the characterization of solvable graphs. To this end, different graph operations, such as joins and Cartesian products, have been considered in the past. In this article, we continue this venue of research by investigating line graphs. Instead of playing peg solitaire on the line graph $L(G)$ of a graph $G$, we introduce a related game called stick solitaire and play it on $G$. This game is examined on several well-known graph classes, for example complete graphs and windmills. In particular, we prove that most of them are stick-solvable. We also present a family of graphs which contains unsolvable graphs in stick solitaire. Naturally, the Fool's stick solitaire number is an object of interest, which we compute for the previously considered graph classes.

Harary and Wiener indices are distance-based topological index. In this paper, we study the relations of graph energy $\varepsilon(G)$ and its Harary index $\textup{H}(G)$ and Wiener index $\textup{W}(G)$. Moreover, for a given graph $G$ we study the lower bound of $\frac{\textup{H}(G)}{\varepsilon(G)}$ and $\frac{\textup{W}(G)}{\varepsilon(G)}$ in terms of number of vertices of $G$.

A hypertree is a special type of connected hypergraph that removes‎ ‎any‎, ‎its hyperedge then results in a disconnected hypergraph‎. ‎Relation between hypertrees (hypergraphs) and trees (graphs) can be helpful to solve real problems in hypernetworks and networks and it is the main tool in this regard‎. ‎The purpose of this paper is to introduce a positive relation (as $\alpha$-relation) on hypertrees that makes a connection between hypertrees and trees‎. ‎This relation is dependent on some parameters such as path‎, ‎length of a path‎, ‎and the intersection of hyperedges‎. ‎For any $q\in \mathbb{N}‎, ‎$ we introduce the concepts of a derivable tree‎, ‎$(\alpha‎, ‎q)$-hypergraph‎, ‎and fundamental $(\alpha‎, ‎q)$-hypertree for the first time in this study and analyze the structures of derivable trees from hypertrees via given positive relation‎. ‎In the final‎, ‎we apply the notions of derivable trees‎, ‎$(\alpha‎, ‎q)$-trees in real optimization problems by modeling hypernetworks and networks based on hypertrees and trees‎, ‎respectively.‎‎‎